package Solution.problem064;

/**
 * @program Leetcode
 * @description: Minimum Path Sum 最小路径和
 * 都需要用动态规划Dynamic Programming来做，这应该算是DP问题中比较简单的一类，
 * 我们维护一个二维的dp数组，其中dp[i][j]表示当前位置的最小路径和，
 * 递推式也容易写出来 dp[i][j] = grid[i][j] + min(dp[i - 1][j],dp[i][j - 1])
 * @create: 2019/06/09 12:51
 */
public class Solution {
    private static  int minPathSum(int[][] grid) {

        /** 基本的边界控制*/
        if(grid==null){
            return 0;
        }
        int row=grid.length;
        if(row==0){
            return 0;
        }
        int col=grid[0].length;
        if(col==0){
            return 0;
        }

        /** 定义一个最短路径计算结果矩阵*/
        int[][] result=new int[row][col];
        result[0][0]=grid[0][0];
        /** 边界路径计算*/
        for(int i=1;i<row;i++){
            result[i][0]=result[i-1][0]+grid[i][0];
        }
        for(int j=1;j<col;j++){
            result[0][j]=result[0][j-1]+grid[0][j];
        }

        /** 非边界计算*/
        for(int i=1;i<row;i++){
            for (int j=1;j<col;j++){
                result[i][j]=Math.min(result[i - 1][j],result[i][j - 1])+grid[i][j];
            }
        }

        return result[row-1][col-1];
    }

    public static void main(String[] args){
        int[][] grid=new int[][]{{},{},{}};
        System.out.println(minPathSum(grid));
        int[][] grid2=new int[][]{};
        System.out.println(minPathSum(grid2));
        int[][] grid3=new int[][]{{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(minPathSum(grid3));

    }
}
